package day5.problem2;

import java.util.*;

//腐烂的苹果(多源BFS)
//https://www.nowcoder.com/practice/54ab9865ce7a45968b126d6968a77f34?tpId=196&tqId=40529&ru=/exam/oj


public class Solution {
     int n, m;
     boolean[][] st;
     int ret = 0;
    public int rotApple (ArrayList<ArrayList<Integer>> grid) {
        n = grid.size();
        m = grid.get(0).size();
        st = new boolean[n][m];
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<m; j++) {
                if(grid.get(i).get(j) == 2) {
                    queue.add(new int[]{i, j});
                }
            }
        }
        int[] xx = {1, -1, 0, 0};
        int[] yy = {0, 0, 1, -1};
        while(!queue.isEmpty()) {
            int size = queue.size();
            while(size-- > 0) {
                int[] t = queue.poll();
                int x = t[0], y = t[1];
                for(int i = 0; i<4; i++) {
                    int dx = x + xx[i], dy = y + yy[i];
                    if(dx >= 0 && dx < n && dy >= 0 && dy < m && !st[dx][dy] && grid.get(dx).get(dy) == 1) {
                        st[dx][dy] = true;
                        queue.add(new int[]{dx, dy});
                    }
                }
            }
             ret++;
        }
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<m; j++) {
                if(grid.get(i).get(j) == 1 && !st[i][j]) {
                    return -1;
                }
            }
        }
        return ret-1;
    }
}